package interview.dynamic;

import java.util.HashMap;
import java.util.Map;

/**
 * lenArr[i] 是以 index=i 结尾的字符串，最大子串的长度
 *
 * Created by yzy on 2021-03-03 17:09
 */
public class LengthOfLongestSubstring {

    public static void main(String[] args) {
        String s1 = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s1));
    }


    public static int lengthOfLongestSubstring(String s) {
        if(s.length()==0 || s==null){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int maxSubLen = 0;
        int currSubLen = 0;
        int subStrStartIdx = 0;
        for(int i=0; i<s.length(); i++){
            char key = s.charAt(i);
            Integer idx = map.get(key);
            if(idx != null && idx >= subStrStartIdx){
                subStrStartIdx = idx+1;
            }

            currSubLen = i - subStrStartIdx + 1;
            maxSubLen = maxSubLen > currSubLen ? maxSubLen : currSubLen;
            map.put(key, i);
        }
        return maxSubLen;
    }













    public static int lengthOfLongestSubstring_2_test(String s) {
        if(s.length()==0 || s==null){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int subStrStartIdx = 0;
        int maxLen = 0;
        for(int i=0; i<s.length(); i++){
            char key = s.charAt(i);
            Integer idx = map.get(key);
            // 找到相同字符，并且在子串中，那么如果想要包含当前i的字符，那就需要把startIdx移动到idx后一位(去掉前面包含的)
            if(idx!=null && idx > subStrStartIdx){
                subStrStartIdx = idx+1;
            }
            int currLen = i - subStrStartIdx + 1;
            maxLen = currLen > maxLen ? currLen : maxLen;
            map.put(key, i);
        }
        return maxLen;
    }
}
